package com.lfg.leetcode.leetcode100;

import com.lfg.leetcode.leetcode0.TreeNode;

public class No124maxPathSum {

    public static void main(String[] args) {
        int ret = maxPathSum(TreeNode.stringToTreeNode("[5,4,8,11,null,13,4,7,2,null,null,null,1]"));
//        int ret = maxPathSum(TreeNode.stringToTreeNode("[-10,9,20,null,null,15,7]"));
        System.out.println("[" + ret + "]");
    }


    public static int maxPathSum(TreeNode root) {
        if (null == root) {
            return 0;
        }
        Result ret = maxSum(root);
        return ret.maxSum;
    }

    public static Result maxSum(TreeNode root) {
        if (root == null) {
            return null;
        }
        Result ret = new Result();
        ret.total = root.val;
        ret.maxSum = ret.total;
        int leftTotal = ret.total;
        int rightTotal = ret.total;

        int leftMax = ret.maxSum;
        int rightMax = ret.maxSum;
        int max = ret.total;
        Result left = maxSum(root.left);
        if (left != null) {
            leftTotal += left.total;
            leftMax = left.maxSum;
            max += left.total;
        }
        Result right = maxSum(root.right);
        if (right != null) {
            rightTotal += right.total;
            rightMax = right.maxSum;
            max += right.total;
        }
        ret.total = Math.max(ret.total, Math.max(leftTotal, rightTotal));
        ret.maxSum = Math.max(Math.max(leftMax, rightMax), Math.max(ret.total, max));
        return ret;
    }

    static class Result {
        public int total;
        public int maxSum;
    }
}
